/** 二叉树类
 *
 */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  /** 二叉树构造函数
   *
   * @param val 数值
   * @param leftNode 左节点
   * @param rightNode 右节点
   */
  constructor(val?: number, left?: TreeNode, right?: TreeNode) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
  //#region 递归遍历
  /** 前序遍历
   *
   * @param node
   * @returns
   */
  static preorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
      if (node === null) return;
      res.push(node.val);
      traverse(node.left, res);
      traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
  }

  /** 中序遍历
   *
   * @param node
   * @returns
   */
  static inorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
      if (node === null) return;
      traverse(node.left, res);
      res.push(node.val);
      traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
  }

  /** 后序遍历
   *
   * @param node
   * @returns
   */
  static postorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
      if (node === null) return;
      traverse(node.left, res);
      traverse(node.right, res);
      res.push(node.val);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
  }
  //#endregion
  //#region 迭代遍历
  // 前序遍历（迭代法）
  static preorderIteration(root: TreeNode | null): number[] {
    let helperStack: (TreeNode | null)[] = [];
    let res: number[] = [];
    let curNode: TreeNode | null;
    if (root === null) return res;
    helperStack.push(root);
    while (helperStack.length > 0) {
      curNode = helperStack.pop()!;
      if (curNode !== null) {
        if (curNode.right !== null) helperStack.push(curNode.right);
        if (curNode.left !== null) helperStack.push(curNode.left);
        helperStack.push(curNode);
        helperStack.push(null);
      } else {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
      }
    }
    return res;
  }

  // 中序遍历（迭代法）
  static inorderIteration(root: TreeNode | null): number[] {
    let helperStack: (TreeNode | null)[] = [];
    let res: number[] = [];
    let curNode: TreeNode | null;
    if (root === null) return res;
    helperStack.push(root);
    while (helperStack.length > 0) {
      curNode = helperStack.pop()!;
      if (curNode !== null) {
        if (curNode.right !== null) helperStack.push(curNode.right);
        helperStack.push(curNode);
        helperStack.push(null);
        if (curNode.left !== null) helperStack.push(curNode.left);
      } else {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
      }
    }
    return res;
  }

  // 后序遍历（迭代法）
  static postorderIteration(root: TreeNode | null): number[] {
    let helperStack: (TreeNode | null)[] = [];
    let res: number[] = [];
    let curNode: TreeNode | null;
    if (root === null) return res;
    helperStack.push(root);
    while (helperStack.length > 0) {
      curNode = helperStack.pop()!;
      if (curNode !== null) {
        helperStack.push(curNode);
        helperStack.push(null);
        if (curNode.right !== null) helperStack.push(curNode.right);
        if (curNode.left !== null) helperStack.push(curNode.left);
      } else {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
      }
    }
    return res;
  }
  //#endregion

  /** 二叉树层序遍历
   *
   * @param root
   * @returns
   */
  static levelOrder(root: TreeNode | null): number[][] {
    let helperQueue: TreeNode[] = [];
    let res: number[][] = [];
    let tempArr: number[] = [];
    if (root !== null) helperQueue.push(root);
    let curNode: TreeNode;
    while (helperQueue.length > 0) {
      for (let i = 0, length = helperQueue.length; i < length; i++) {
        curNode = helperQueue.shift()!;
        tempArr.push(curNode.val);
        if (curNode.left !== null) {
          helperQueue.push(curNode.left);
        }
        if (curNode.right !== null) {
          helperQueue.push(curNode.right);
        }
      }
      res.push(tempArr);
      tempArr = [];
    }
    return res;
  }

  /** 最大深度
   *
   * @param root
   * @returns
   */
  static maxDepth(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    let resDepth: number = 0;
    let tempNode: TreeNode;
    if (root !== null) helperQueue.push(root);
    while (helperQueue.length > 0) {
      resDepth++;
      for (let i = 0, length = helperQueue.length; i < length; i++) {
        tempNode = helperQueue.shift()!;
        if (tempNode.left) helperQueue.push(tempNode.left);
        if (tempNode.right) helperQueue.push(tempNode.right);
      }
    }
    return resDepth;
  }

  /** 最小深度
   *
   * @param root
   * @returns
   */
  static minDepth(root: TreeNode | null): number {
    let helperQueue: TreeNode[] = [];
    let resMin: number = 0;
    let tempNode: TreeNode;
    if (root !== null) helperQueue.push(root);
    while (helperQueue.length > 0) {
      resMin++;
      for (let i = 0, length = helperQueue.length; i < length; i++) {
        tempNode = helperQueue.shift()!;
        if (tempNode.left === null && tempNode.right === null) return resMin;
        if (tempNode.left !== null) helperQueue.push(tempNode.left);
        if (tempNode.right !== null) helperQueue.push(tempNode.right);
      }
    }
    return resMin;
  }

  /** 反转二叉树
   *
   * @param root
   * @returns
   */
  static invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return root;
    let tempNode: TreeNode | null = root.left;
    root.left = root.right;
    root.right = tempNode;
    TreeNode.invertTree(root.left);
    TreeNode.invertTree(root.right);
    return root;
  }

  //二叉搜索树的最近公共祖先;
  static lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode | null,
    q: TreeNode | null
  ): TreeNode | null {
    if (root!.val > p!.val && root!.val > q!.val)
      return TreeNode.lowestCommonAncestor(root!.left, p, q);
    if (root!.val < p!.val && root!.val < q!.val)
      return TreeNode.lowestCommonAncestor(root!.right, p, q);
    return root;
  }

  /** 二叉搜索树中的众数
   *
   * @param root
   * @returns
   */
  findMode(root: TreeNode | null): number[] {
    if (root === null) return [];
    const countMap: Map<number, number> = new Map();
    function traverse(root: TreeNode | null): void {
      if (root === null) return;
      countMap.set(root.val, (countMap.get(root.val) || 0) + 1);
      traverse(root.left);
      traverse(root.right);
    }
    traverse(root);
    const countArr: number[][] = Array.from(countMap);
    countArr.sort((a, b) => {
      return b[1] - a[1];
    });
    const resArr: number[] = [];
    const maxCount: number = countArr[0][1];
    for (let i of countArr) {
      if (i[1] === maxCount) resArr.push(i[0]);
    }
    return resArr;
  }

  /** 取得最小绝对差
   *
   * @param root
   * @returns
   */
  static getMinimumDifference(root: TreeNode | null): number {
    let helperArr: number[] = [];
    function recur(root: TreeNode | null): void {
      if (root === null) return;
      recur(root.left);
      helperArr.push(root.val);
      recur(root.right);
    }
    recur(root);
    let resMin: number = Infinity;
    for (let i = 0, length = helperArr.length; i < length - 1; i++) {
      resMin = Math.min(resMin, helperArr[i + 1] - helperArr[i]);
    }
    return resMin;
  }

  /** 验证二叉搜索树
   *
   * @param root
   * @returns
   */
  static isValidBST(root: TreeNode | null): boolean {
    const traversalArr: number[] = [];
    function inorderTraverse(root: TreeNode | null): void {
      if (root === null) return;
      inorderTraverse(root.left);
      traversalArr.push(root.val);
      inorderTraverse(root.right);
    }
    inorderTraverse(root);
    for (let i = 0, length = traversalArr.length; i < length - 1; i++) {
      if (traversalArr[i] >= traversalArr[i + 1]) return false;
    }
    return true;
  }

  /** 二叉搜索树中的搜索
   *
   * @param root
   * @param val
   * @returns
   */
  static searchBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null || root.val === val) return root;
    if (root.val < val) return TreeNode.searchBST(root.right, val);
    if (root.val > val) return TreeNode.searchBST(root.left, val);
    return null;
  }

  /** 二叉搜索树中的插入操作
   *
   * @param root
   * @param val
   * @returns
   */
  static insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) return new TreeNode(val);
    if (root.val > val) {
      root.left = TreeNode.insertIntoBST(root.left, val);
    } else {
      root.right = TreeNode.insertIntoBST(root.right, val);
    }
    return root;
  }

  /** 删除二叉搜索树中的节点
   *
   * @param root
   * @param key
   * @returns
   */
  static deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (root === null) return null;
    if (root.val === key) {
      if (root.left === null && root.right === null) return null;
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;
      let curNode: TreeNode = root.right;
      while (curNode.left !== null) {
        curNode = curNode.left;
      }
      curNode.left = root.left;
      return root.right;
    }
    if (root.val > key) root.left = TreeNode.deleteNode(root.left, key);
    if (root.val < key) root.right = TreeNode.deleteNode(root.right, key);
    return root;
  }

  /** 将有序数组转换为二叉搜索树
   *
   * @param nums
   * @returns
   */
  static sortedArrayToBST(nums: number[]): TreeNode | null {
    function recur(
      nums: number[],
      left: number,
      right: number
    ): TreeNode | null {
      if (left > right) return null;
      let mid: number = Math.floor((left + right) / 2);
      const root: TreeNode = new TreeNode(nums[mid]);
      root.left = recur(nums, left, mid - 1);
      root.right = recur(nums, mid + 1, right);
      return root;
    }
    return recur(nums, 0, nums.length - 1);
  }
}
